/LMAR=0/XLINE=4/FONT#0=BAXL30/FONT#1=BAXB30/FONT#2=BAXI30[  P,JRA]/FONT#3=SUB/FONT#4=SET1/FONT#5=NGR20/FONT#6=GRK30/FONT#7=SUP/FONT#8=SPEC[  P,JRA]/FONT#11=METSB/FONT#0=BAXL30/FONT#1=BAXB30/FONT#2=BAXI30/FONT#3=SUB/FONT#4=SET1/FONT#5=NGR20/FONT#6=GRK30/FONT#7=SUP/FONT#9=BAXB30/FONT#11=FIX30
␈↓ α␈↓␈↓ r␈↓CONTENTS  ␈↓

␈↓"β␈↓ α␈↓	pub is a crock
␈↓ α␈↓␈↓ i␈↓CONTENTS  i␈↓

␈↓"β␈↓ α␈↓	pub is more of a crock
␈↓ α␈↓␈↓ i␈↓CONTENTS  i␈↓

␈↓"β␈↓ α␈↓	page it
␈↓ α␈↓␈↓ `␈↓CONTENTS  ii␈↓








␈↓ α␈↓	␈↓ ε"T A B L E   O F   C O N T E N T S











␈↓ α␈↓␈↓↓{secname}␈↓ {{page!}␈↓{skip; }
␈↓ α␈↓␈↓ λ,␈↓  ␈↓
␈↓ α␈↓␈↓ 
{␈↓  1␈↓

␈↓"β␈↓ α␈↓␈↓ ∧n␈↓↓The Post Correspondence Problem as a Question of Ambiguity␈↓






␈↓"β␈↓ α␈↓In␈α
courses␈αdealing␈α
with␈αcomputability␈α
the␈α
Post␈αCorrespondence␈α
Problem␈α(PCP)␈α
is␈α
usually␈αintroduced␈α
by␈αdefinition,␈α
shown
␈↓ α␈↓to␈αbe␈αunsolvable␈αby␈αreducing␈αit␈αto␈αthe␈αhalting␈αproblem␈α(Minsky,␈αManna),␈αand␈αdisposed␈αof␈αas␈αyet␈αanother␈αexample␈αof␈αan
␈↓ α␈↓unsolvable␈αclass␈αof␈αquestions.␈α Rarely␈αdo␈αstudents␈αget␈α
any␈αreal␈αunderstanding␈αof␈αwhat␈αthe␈αPCP␈αis␈αand␈α
where␈αdifficulties
␈↓ α␈↓lie␈α∂in␈α∂finding␈α∞an␈α∂answer␈α∂to␈α∂a␈α∞specific␈α∂example.␈α∂ A␈α∂partial␈α∞decision␈α∂procedure␈α∂can␈α∂be␈α∞very␈α∂helpful␈α∂in␈α∂developing␈α∞this
␈↓ α␈↓understanding.
␈↓"β␈↓ α␈↓␈↓ α`The␈α
Sardinas-Patterson␈α∞test␈α
for␈α∞ambiguity␈α
of␈α
a␈α∞code␈α
provides␈α∞an␈α
algorithm␈α
that␈α∞can␈α
be␈α∞modified␈α
to␈α∞search␈α
for
␈↓ α␈↓answers␈αto␈αany␈αspecific␈α
example␈αof␈αthe␈αPCP.␈α
 First,␈αwe␈αpresent␈αthe␈αSardinas-Patterson␈α
test.␈α Secondly,␈αwe␈αshow␈α
how␈αthe
␈↓ α␈↓test␈αcan␈αbe␈αmodified␈αto␈αsolve␈αa␈αproblem␈αsimilar␈αbut␈αnot␈αequivalent␈αto␈αthe␈αPCP.␈α We␈αthen␈αstate␈αthe␈αPost␈αCorrespondence
␈↓ α␈↓Problem itself and develop a partial decision procedure by a further modification to the algorithm.␈↓π 1␈↓


␈↓"β␈↓ α␈↓␈↓ ε3␈↓	Section 1: Sardinas Patterson Test␈↓
␈↓"β␈↓ α␈↓␈↓ α`A␈α
␈↓αcode␈↓␈α
is␈αa␈α
set␈α
of␈αcode␈α
words,␈α
or␈αstrings,␈α
from␈α
some␈αgiven␈α
finite␈α
alphabet,␈αe.g.,␈α
for␈α
the␈αalphabet␈α
{0,␈α
1},␈α
a␈αsample
␈↓ α␈↓code␈α∞is␈α
{001,␈α∞01,␈α∞0100,␈α
101}.␈α∞ A␈α∞code␈α
is␈α∞ambiguous␈α∞if␈α
there␈α∞exists␈α
a␈α∞string␈α∞which␈α
can␈α∞be␈α∞interpreted,␈α
or␈α∞parsed,␈α∞in␈α
two
␈↓ α␈↓different␈α⊃ways.␈α∩For␈α⊃example,␈α⊃with␈α∩the␈α⊃given␈α⊃code,␈α∩the␈α⊃string␈α∩"0100101"␈α⊃can␈α⊃be␈α∩parsed␈α⊃as␈α⊃a␈α∩string␈α⊃of␈α∩three␈α⊃words,
␈↓ α␈↓"01.001.01",␈αor␈αas␈αa␈αstring␈αof␈αtwo␈αwords,␈α"0100.101".␈α The␈αSardinas-Patterson␈αtest␈αprovides␈αan␈αalgorithm␈αfor␈αdetermining
␈↓ α␈↓whether␈α∞or␈α∂not␈α∞a␈α∞given␈α∂code␈α∞is␈α∂ambiguous,␈α∞and,␈α∞if␈α∂it␈α∞is,␈α∞the␈α∂test␈α∞also␈α∂provides␈α∞the␈α∞means␈α∂of␈α∞constructing␈α∂an␈α∞example
␈↓ α␈↓ambiguous string.
␈↓"β␈↓ α␈↓␈↓ α`If␈α
␈↓εa␈↓=␈↓εbg␈↓,␈αwhere␈α
␈↓εa␈↓,␈α
␈↓εb␈↓,␈αand␈α
␈↓εg␈↓␈α
are␈αstrings,␈α
then␈α
␈↓εb␈↓␈αis␈α
said␈α
to␈αbe␈α
a␈α
"prefix"␈αof␈α
␈↓εa␈↓␈α
and␈α␈↓εg␈↓␈α
is␈α
called␈αthe␈α
"tail".␈α
 If␈αthere
␈↓ α␈↓exists␈αan␈αambiguous␈α
string,␈αthen␈αit␈αmust␈α
begin␈αwith␈αa␈αcode␈α
word␈αwhich␈αis␈α
the␈αprefix␈αof␈αanother␈α
code␈αword.␈αThe␈αtail␈α
must
␈↓ α␈↓then␈α∞form␈α∞a␈α∞prefix␈α∞of␈α∞some␈α∞code␈α∂word.␈α∞ With␈α∞each␈α∞tail␈α∞we␈α∞keep␈α∞track␈α∞of,␈α∂we␈α∞are␈α∞saying␈α∞that␈α∞there␈α∞is␈α∞a␈α∞string␈α∂that␈α∞is
␈↓ α␈↓ambiguous up to a point, but we have this overhang, this tail, which must still be incorporated as a legal code sequence.
␈↓"β␈↓ α␈↓␈↓ α`␈↓↓Sardinas-Patterson Test␈↓␈↓π 2␈↓:
␈↓"β␈↓ α␈↓␈↓ α`We make a table, entering the code words in column 0.  We add entries in the rest
␈↓"β␈↓ α␈↓␈↓ α`of the columns according to the following rules:
␈↓"β␈↓ α␈↓␈↓ α`     
␈↓"β␈↓ α␈↓␈↓ α`        1)  to construct column 1, check column 0 to see if any of the code words
␈↓"β␈↓ α␈↓␈↓ α`        is a prefix of any other code word.
␈↓"β␈↓ α␈↓␈↓ α`                a)  if there is no such pair of code words, then the code is not
␈↓"β␈↓ α␈↓␈↓ α`                ambiguous.
␈↓"β␈↓ α␈↓␈↓ α`                b)  for each such pair that can be found, enter the "tail" in
␈↓"β␈↓ α␈↓␈↓ α`                column 1, and proceed.
␈↓"β␈↓ α␈↓␈↓ α`    
␈↓"β␈↓ α␈↓␈↓ α`        2)  to construct column n+1 (n≥1):
␈↓"β␈↓ α␈↓␈↓ α`                a)  examine column n for any word13hich is a prefix of some word
␈↓"β␈↓ α␈↓␈↓ α`                in column 0.  For each such pair, enter the tail in column n+1.
␈↓"β␈↓ α␈↓␈↓ α`                b) Examine column 0 for any word13hich is a prefix of some word
␈↓"β␈↓ α␈↓________________
␈↓"β␈↓ α␈↓␈↓ α`␈↓π 1␈↓It is suggested that anyone already familiar with the Sardinas-Patterson test skip to section 2.
␈↓"β␈↓ α␈↓␈↓ α`␈↓π 2␈↓The␈α∂algorithm␈α⊂given␈α∂was␈α∂presented␈α⊂by␈α∂D.␈α⊂Huffman␈α∂in␈α∂an␈α⊂Information␈α∂Sciences␈α∂course␈α⊂at␈α∂the␈α⊂University␈α∂of
␈↓ α␈↓California at Santa Cruz.
␈↓ α␈↓␈↓ 
{␈↓  2␈↓

␈↓"β␈↓ α␈↓␈↓ α`                in column n.  For each such pair, enter the tail in column n+1.
␈↓"β␈↓ α␈↓␈↓ α`     
␈↓"β␈↓ α␈↓␈↓ α`        3)  Continue the process of creating new columns by computing tails until:
␈↓"β␈↓ α␈↓␈↓ α`                a)  No entries are found for a new column - in this case the code
␈↓"β␈↓ α␈↓␈↓ α`                is not ambiguous.
␈↓"β␈↓ α␈↓␈↓ α`                b)  A tail created in some column is one of the original code
␈↓"β␈↓ α␈↓␈↓ α`                words. In this case the code is ambiguous and an example can be
␈↓"β␈↓ α␈↓␈↓ α`                constructed from the entries in the table.
␈↓"β␈↓ α␈↓␈↓ α`                c)  A column is repeated - at this point we know we shall be
␈↓"β␈↓ α␈↓␈↓ α`                forever repeating the same pattern, as the construction of new
␈↓"β␈↓ α␈↓␈↓ α`                columns depends only on the single previous column and the
␈↓"β␈↓ α␈↓␈↓ α`                original code in column 0.  In this case the code is again
␈↓"β␈↓ α␈↓␈↓ α`                unambiguous.
␈↓"β␈↓ α␈↓␈↓ α`     
␈↓"β␈↓ α␈↓For␈αexample,␈αfor␈αthe␈αcode␈αgiven␈αabove,␈αthe␈αalgorithm␈αyields␈αthe␈αtable␈αof␈αFigure␈α1.␈α The␈αambiguous␈αstring␈α"0100101"␈αcan
␈↓ α␈↓be constructed by tracing the history of the marked entry. It yields the two parses "01.001.01." and "0100.101.".
␈↓"β␈↓ α␈↓␈↓ α`                  0      1       2       3
␈↓"β␈↓ α␈↓␈↓ α`                ______________________________
␈↓"β␈↓ α␈↓␈↓ α`                001     00       1      01 *** this tail is also a code word!***
␈↓"β␈↓ α␈↓␈↓ α`                 01
␈↓"β␈↓ α␈↓␈↓ α`               0100
␈↓"β␈↓ α␈↓␈↓ α`                101
␈↓"β␈↓ α␈↓␈↓ α`                                 Figure 1.
␈↓"β␈↓ α␈↓The␈α
number␈αof␈α
columns␈αcreated␈α
in␈αthis␈α
process␈αgives␈α
an␈αindication␈α
of␈αthe␈α
delay␈αrequired,␈α
in␈αthe␈α
worst␈αcase,␈α
to␈αresolve␈α
any
␈↓ α␈↓temporary␈α
ambiguity␈α
which␈α
may␈α
occur␈α
even␈α
when␈α
the␈α
code␈α
itself␈α
is␈α
unambiguous.␈α
 If␈α
the␈α
algorithm␈α
stops␈α
in␈αcondition␈α
3)c),
␈↓ α␈↓then␈α∂there␈α∂is␈α∂no␈α∂bound␈α∂on␈α∂this␈α∂delay;␈α∂we␈α∂may␈α∂have␈α∂to␈α∂wait␈α∂until␈α∂the␈α∂entire␈α∂message␈α∂is␈α∂received␈α∂before␈α∂we␈α⊂can␈α∂start
␈↓ α␈↓decoding it.


␈↓"β␈↓ α␈↓␈↓ εr␈↓	Section 2: Modified PCP␈↓
␈↓"β␈↓ α␈↓␈↓ α`Suppose␈α
we␈αare␈α
given␈α
a␈αfinite␈α
set␈α
of␈αordered␈α
pairs␈αof␈α
strings␈α
{(␈↓εa␈↓β1␈↓,␈↓εb␈↓β1␈↓),␈α...,(␈↓εa␈↓βn␈↓,␈↓εb␈↓βn␈↓)}␈α
and␈α
asked␈αto␈α
determine␈αwhether␈α
or
␈↓ α␈↓not␈αindices␈αi␈↓β1␈↓,␈α...,␈αi␈↓βk␈↓␈αand␈α
j␈↓β1␈↓,␈α...,␈αj␈↓βr␈↓␈αexist␈αsuch␈αthat␈α
␈↓εa␈↓βi␈↓#v1␈↓#␈↓...␈↓εa␈↓βi␈↓#vk␈↓#␈↓␈α=␈α␈↓εb␈↓βj␈↓#v1␈↓#␈↓...␈↓εb␈↓βj␈↓#vr␈↓#␈↓.␈α That␈αis,␈αwe␈α
must␈αbe␈αable␈αto␈αdecide␈αwhether␈αthere␈α
exists
␈↓ α␈↓a string that can be interpreted as consisting either entirely of ␈↓εa␈↓'s or entirely of ␈↓εb␈↓'s, and produce the string if it does exist.
␈↓"β␈↓ α␈↓␈↓ α`This␈α
time␈αwe␈α
make␈αa␈α
table␈α
with␈αpairs␈α
of␈αcolumns␈α
since␈α
we␈αneed␈α
to␈αkeep␈α
the␈α
␈↓εa␈↓'s␈αseparated␈α
from␈αthe␈α
␈↓εb␈↓'s.␈α
 To␈αget
␈↓ α␈↓started␈α
we␈α
must␈αfind␈α
an␈α
␈↓εa␈↓βi␈↓␈αand␈α
␈↓εb␈↓βj␈↓␈α
such␈α
that␈αone␈α
is␈α
the␈αprefix␈α
of␈α
the␈α
other.␈α The␈α
tail␈α
must␈αthen␈α
be␈α
interpretable␈α
as␈αthe
␈↓ α␈↓beginning of either a string of ␈↓εa␈↓'s (if ␈↓εa␈↓βi␈↓ was the prefix of ␈↓εb␈↓βj␈↓) or a string of ␈↓εb␈↓'s (if ␈↓εb␈↓βj␈↓ was the prefix of ␈↓εa␈↓βi␈↓).
␈↓"β␈↓ α␈↓␈↓ α`Suppose␈αthat␈αwe␈αhave␈αalready␈αlisted␈αn␈αcolumns␈αin␈αthe␈αtable.␈αEach␈αentry␈α␈↓εg␈↓␈αin␈αcolumn␈αn␈↓βα␈↓␈αindicates␈αthat␈αa␈αstring␈α␈↓εs␈↓
␈↓ α␈↓can␈αbe␈αconstructed␈αwhich␈αmay␈αbe␈αinterpreted␈αas␈αconsisting␈αentirely␈αof␈α␈↓εb␈↓'s,␈αor␈αentirely␈αof␈α␈↓εa␈↓'s␈αwith␈αthe␈αstring␈α␈↓εg␈↓␈αon␈αthe␈αend.
␈↓ α␈↓That␈αis,␈αthe␈αstring␈α␈↓εs␈↓ = a␈↓β1␈↓...a␈↓βk␈↓a␈↓βk+1␈↓...a␈↓βn␈↓␈α(where␈αeach␈αa␈↓βi␈↓␈αis␈αa␈αletter␈αof␈αthe␈αcode␈αalphabet)␈αis␈αthe␈αsame␈αas␈α␈↓εb␈↓βj␈↓#v1␈↓#␈↓...␈↓εb␈↓βj␈↓#vm␈↓#␈↓␈αfor␈αsome␈α␈↓βj␈↓#v1␈↓#␈↓...␈↓βj␈↓#vm␈↓#␈↓,
␈↓ α␈↓and the same as ␈↓εa␈↓βi␈↓#v1␈↓#␈↓...␈↓εa␈↓βi␈↓#vp␈↓#␈↓εg␈↓ for some ␈↓βi␈↓#v1␈↓#␈↓...␈↓βi␈↓#vp␈↓#␈↓.
␈↓"β␈↓ α␈↓␈↓ α`If␈α␈↓εg␈↓␈αitself␈αis␈αan␈α␈↓εa␈↓,␈αthen␈αwe␈αare␈αdone;␈αbut␈αif␈αnot,␈αwe␈αmust␈αcontinue␈αour␈αsearch.␈α If␈α␈↓εg␈↓␈αis␈αa␈αprefix␈αof␈αan␈α␈↓εa␈↓βi␈↓,␈αthen␈αwe
␈↓ α␈↓extend␈α
our␈α
string␈αof␈α
␈↓εa␈↓'s␈α
by␈αthat␈α
␈↓εa␈↓βi␈↓,␈α
resulting␈αin␈α
the␈α
string␈αwe␈α
had␈α
before␈αwith␈α
the␈α
addition␈αof␈α
the␈α
new␈αtail␈α
on␈α
the␈αend.
␈↓ α␈↓This␈αstring␈α
can␈αbe␈α
interpreted␈αas␈α
consisting␈αentirely␈α
of␈α␈↓εa␈↓'s,␈α
or␈αentirely␈α
of␈α␈↓εb␈↓'s␈α
with␈αthe␈α
new␈αtail␈α
appended␈αto␈α
the␈αend.␈α
Thus,
␈↓ α␈↓we must add the new tail to the column (n+1)␈↓ββ␈↓.
␈↓"β␈↓ α␈↓␈↓ α`If␈αsome␈α␈↓εa␈↓βi␈↓␈αis␈αa␈αprefix␈αof␈α␈↓εg␈↓,␈αthen␈αwe␈αhave␈α
extended␈αour␈α␈↓εa␈↓-interpretation␈αof␈α␈↓εs␈↓,␈αand␈αthe␈αnew␈αtail␈αis␈αthe␈α"leftover"␈α
in
␈↓ α␈↓the same sense that ␈↓εg␈↓ was.  Thus we add the new tail to column (n+1)␈↓βα␈↓.
␈↓"β␈↓ α␈↓␈↓ α`We␈α
do␈α
an␈α
analogous␈α
examination␈α
of␈α
column␈α
n␈↓ββ␈↓.␈α
 If␈α
we␈α
ever␈αfind␈α
an␈α
␈↓εa␈↓βi␈↓␈α
in␈α
some␈α
column␈α
n␈↓βα␈↓,␈α
or␈α
a␈α
␈↓εb␈↓βj␈↓␈α
in␈αsome␈α
column
␈↓ α␈↓␈↓ 
{␈↓  3␈↓

␈↓"β␈↓ α␈↓n␈↓ββ␈↓,␈α
then␈αwe␈α
are␈αthrough.␈α
 There␈αis␈α
a␈αsolution␈α
string␈αand␈α
it␈α
can␈αbe␈α
constructed␈αby␈α
tracing␈αthe␈α
history␈αof␈α
the␈αentry␈α
␈↓εa␈↓βi␈↓␈αin␈α
n␈↓βα␈↓,
␈↓ α␈↓or ␈↓εb␈↓βj␈↓ in n␈↓ββ␈↓, as the case may be.
␈↓"β␈↓ α␈↓␈↓ α`This discussion is summarized as the following algorithm:
␈↓"β␈↓ α␈↓␈↓ α`    
␈↓"β␈↓ α␈↓␈↓ α`        1)  Enter the ␈↓εa␈↓'s and ␈↓εb␈↓'s in columns 0␈↓βα␈↓ and 0␈↓ββ␈↓, respectively.
␈↓"β␈↓ α␈↓␈↓ α`     
␈↓"β␈↓ α␈↓␈↓ α`        2)  Create columns 1␈↓βα␈↓ and 1␈↓ββ␈↓ :
␈↓"β␈↓ α␈↓␈↓ α`                a)  If any ␈↓εa␈↓βi␈↓ is a prefix of any ␈↓εb␈↓βj␈↓, enter the tail in 1␈↓βα␈↓.
␈↓"β␈↓ α␈↓␈↓ α`                b)  If any ␈↓εb␈↓βi␈↓ is a prefix of any ␈↓εa␈↓βj␈↓, enter the tail in 1␈↓ββ␈↓.
␈↓"β␈↓ α␈↓␈↓ α`    
␈↓"β␈↓ α␈↓␈↓ α`        3)  To create columns (n+1)␈↓βα␈↓ and (n+1)␈↓ββ␈↓ :
␈↓"β␈↓ α␈↓␈↓ α`                a1)  If any string in n␈↓βα␈↓ is a prefix of any ␈↓εa␈↓βi␈↓,
␈↓"β␈↓ α␈↓␈↓ α`                enter the tail in (n+1)␈↓ββ␈↓.
␈↓"β␈↓ α␈↓␈↓ α`                a2)  If any ␈↓εa␈↓βi␈↓ is a prefix of any string in n␈↓βα␈↓,
␈↓"β␈↓ α␈↓␈↓ α`                enter the tail in (n+1)␈↓βα␈↓.
␈↓ α␈↓␈↓ 
{␈↓  4␈↓

␈↓"β␈↓ α␈↓␈↓ α`                b1)  If any string in n␈↓ββ␈↓ is a prefix of any ␈↓εb␈↓βi␈↓,
␈↓"β␈↓ α␈↓␈↓ α`                enter the tail in (n+1)␈↓βα␈↓.
␈↓"β␈↓ α␈↓␈↓ α`                b2)  If any ␈↓εb␈↓βi␈↓ is a prefix of any string in n␈↓ββ␈↓,
␈↓"β␈↓ α␈↓␈↓ α`                enter the tail in (n+1)␈↓ββ␈↓.
␈↓"β␈↓ α␈↓␈↓ α`    
␈↓"β␈↓ α␈↓␈↓ α`        4)  Continue creating new columns according to step 3) until one of the
␈↓"β␈↓ α␈↓␈↓ α`          following conditions occurs:
␈↓"β␈↓ α␈↓␈↓ α`                a)  The process closes out, that is, the entries in n␈↓βα␈↓ and n␈↓ββ␈↓
␈↓"β␈↓ α␈↓␈↓ α`                  are such that the columns (n+1)␈↓βα␈↓ and (n+1)␈↓ββ␈↓ are empty.  In
␈↓"β␈↓ α␈↓␈↓ α`                  this case we can say that no solution is possible.
␈↓"β␈↓ α␈↓␈↓ α`                b)  Some column n␈↓βα␈↓ contains an ␈↓εa␈↓βi␈↓, or some column n␈↓ββ␈↓ contains
␈↓"β␈↓ α␈↓␈↓ α`                  a ␈↓εb␈↓βi␈↓; then a solution exists and can be found by tracing the
␈↓"β␈↓ α␈↓␈↓ α`                  history of such an entry through the table.
␈↓"β␈↓ α␈↓␈↓ α`                c)  A pattern of columns develops which will continue infinitely,
␈↓"β␈↓ α␈↓␈↓ α`                  that is, an ␈↓εa␈↓-␈↓εb␈↓ pair of columns is repeated; then there is no
␈↓"β␈↓ α␈↓␈↓ α`                  solution. New columns depend only on the single previous pair of
␈↓"β␈↓ α␈↓␈↓ α`                  columns and the original columns 0␈↓βα␈↓ and 0␈↓ββ␈↓. Therefore
␈↓"β␈↓ α␈↓␈↓ α`                  once any n␈↓βα␈↓-n␈↓ββ␈↓ pair of columns is repeated, the same
␈↓"β␈↓ α␈↓␈↓ α`                  columns will follow the pair ad infinitum.
␈↓"β␈↓ α␈↓␈↓ α`One␈α
of␈α
the␈α
conditions␈α
4)a)␈α
-␈α
4)c)␈α
is␈α
guaranteed␈α
to␈α
occur.␈α
 Since␈α
"tails"␈α
have␈α
length␈α
less␈α
than␈α
some␈α
code,␈α
and␈α
there␈α
is
␈↓ α␈↓a␈α∞maximum␈α∂length␈α∞among␈α∞the␈α∂␈↓εa␈↓βi␈↓␈α∞and␈α∂␈↓εb␈↓βi␈↓,␈α∞there␈α∞is␈α∂a␈α∞maximum␈α∞tail␈α∂length,␈α∞and␈α∂thus␈α∞a␈α∞finite␈α∂number␈α∞of␈α∂possible␈α∞tails.
␈↓ α␈↓Therefore, only a finite number of n␈↓βα␈↓-n␈↓ββ␈↓ column pairs is possible.
␈↓"β␈↓ α␈↓␈↓ ε
␈↓	Section 3: Post Correspondence Problem␈↓
␈↓"β␈↓ α␈↓␈↓ α`The␈α∂difference␈α∂between␈α∂the␈α∂problem␈α∂stated␈α∂above␈α⊂and␈α∂the␈α∂Post␈α∂Correspondence␈α∂Problem␈α∂is␈α∂that␈α∂we␈α⊂were␈α∂not
␈↓ α␈↓restricted␈αto␈α
using␈αthe␈α
same␈αindexing␈αsequence␈α
for␈αboth␈α
␈↓εa␈↓'s␈αand␈α␈↓εb␈↓'s.␈α
The␈αfollowing␈α
statement␈αof␈αthe␈α
PCP␈αis␈α
taken␈αfrom
␈↓ α␈↓Minsky.
␈↓"β␈↓ α␈↓␈↓ β ␈↓↓Post Correspondence Problem:␈↓
␈↓"β␈↓ α␈↓␈↓ β Given␈α∞an␈α∞alphabet␈α∞A␈α∞and␈α∞a␈α∞finite␈α∞set␈α∞of␈α∞pairs␈α∞of␈α∞words␈α∞(␈↓εa␈↓βi␈↓,␈α∞␈↓εb␈↓βi␈↓)␈α∞in␈α∞the␈α∞alphabet␈α∞A,␈α∞is␈α∞there␈α∞a
␈↓ α␈↓␈↓ β sequence i␈↓β1␈↓, i␈↓β2␈↓, ..., i␈↓βn␈↓ of selections such that the strings
␈↓"β␈↓ α␈↓␈↓ εx␈↓εa␈↓βi␈↓#v1␈↓#␈↓εa␈↓βi␈↓#v2␈↓#␈↓...␈↓εa␈↓βi␈↓#vn␈↓#␈↓ and ␈↓εb␈↓βi␈↓#v1␈↓#␈↓εb␈↓βi␈↓#v2␈↓#␈↓...␈↓εb␈↓βi␈↓#vn␈↓#␈↓
␈↓"β␈↓ α␈↓␈↓ β formed by concatenating--writing down in order--corresponding ␈↓εa␈↓'s and ␈↓εb␈↓'s are identical?
␈↓"β␈↓ α␈↓␈↓ α`We␈α∞can␈α∂modify␈α∞the␈α∂table␈α∞building␈α∂procedure␈α∞further␈α∂to␈α∞search␈α∞for␈α∂a␈α∞solution␈α∂to␈α∞the␈α∂PCP,␈α∞providing␈α∂a␈α∞partial
␈↓ α␈↓decision␈αprocedure.␈α
 If␈αa␈αsolution␈α
exists,␈αthen␈αwe␈α
will␈αfind␈αit,␈α
but␈αif␈αthere␈α
is␈αno␈αsolution␈α
we␈αmay␈αend␈α
up␈αlooking␈αforever␈α
as
␈↓ α␈↓we␈α
lose␈α
the␈α
guarantee␈α
of␈α
termination␈α
provided␈α
by␈α
the␈α
algorithm␈α
above.␈α
 As␈α
an␈α
example,␈α
we␈α
construct␈α
a␈α
solution␈α
for␈αthe␈α
set
␈↓ α␈↓of pairs {(1,111), (10111,10), (10,0)} in Figure 2.
␈↓"β␈↓ α␈↓␈↓ α`We␈α
again␈α
build␈α
a␈α
table␈α
with␈α
column␈α
pairs.␈α
 This␈α
time,␈α
to␈α
get␈α
started␈α
we␈α
must␈α
find␈α
an␈α
␈↓εa␈↓βi␈↓␈α
and␈α
␈↓εb␈↓βi␈↓␈α
(with␈α
the␈α␈↓αsame␈↓
␈↓ α␈↓index)␈αsuch␈αthat␈αone␈αis␈αa␈αprefix␈αof␈αthe␈αother.␈α As␈αwe␈αcontinue␈αlisting␈αcolumns,␈αwe␈αmust␈αbe␈αcareful␈αto␈αensure␈αthat␈αwe␈αare
␈↓ α␈↓constructing␈αa␈αstring␈αinterpretable␈αas␈αa␈αsequence␈αof␈α␈↓εa␈↓βi␈↓'s␈αand␈αalso␈αas␈αthe␈α␈↓αsame␈αsequence␈↓␈αof␈α␈↓εb␈↓βi␈↓'s.␈αEvery␈αtime␈αwe␈αmake␈αuse␈αof
␈↓ α␈↓an ␈↓εa␈↓βi␈↓ we must also be able to use the corresponding ␈↓εb␈↓βi␈↓.
␈↓"β␈↓ α␈↓␈↓ α`        1)  Enter the ␈↓εa␈↓'s and ␈↓εb␈↓'s in columns 0␈↓βα␈↓ and 0␈↓ββ␈↓, respectively, being
␈↓"β␈↓ α␈↓␈↓ α`          careful to enter them in order.
␈↓"β␈↓ α␈↓␈↓ α`    
␈↓"β␈↓ α␈↓␈↓ α`        2)  Create columns 1␈↓βα␈↓ and 1␈↓ββ␈↓:
␈↓"β␈↓ α␈↓␈↓ α`                a)  If any ␈↓εa␈↓βi␈↓ is a prefix of ␈↓εb␈↓βi␈↓ (note the same index is required),
␈↓"β␈↓ α␈↓␈↓ α`                  then enter the tail in 1␈↓βα␈↓.
␈↓"β␈↓ α␈↓␈↓ α`                b)  If any ␈↓εb␈↓βi␈↓ is a prefix of the corresponding ␈↓εa␈↓βi␈↓, then enter the
␈↓"β␈↓ α␈↓␈↓ α`                  tail in 1␈↓ββ␈↓.
␈↓"β␈↓ α␈↓␈↓ α`     
␈↓"β␈↓ α␈↓␈↓ α`        3)  Create columns (n+1)␈↓βα␈↓ and (n+1)␈↓ββ␈↓:
␈↓ α␈↓␈↓ 
{␈↓  5␈↓

␈↓"β␈↓ α␈↓␈↓ α`                a1)  If any string in n␈↓βα␈↓ is an ␈↓εa␈↓βi␈↓, write the corresponding ␈↓εb␈↓βi␈↓ in
␈↓"β␈↓ α␈↓␈↓ α`                   column (n+1)␈↓βα␈↓.
␈↓"β␈↓ α␈↓␈↓ α`                a2)  If any string in n␈↓βα␈↓ is a prefix of any ␈↓εa␈↓βi␈↓, check the tail:
␈↓"β␈↓ α␈↓␈↓ α`                          i)  If the tail is the corresponding ␈↓εb␈↓βi␈↓, then we have
␈↓"β␈↓ α␈↓␈↓ α`                            a solution!
␈↓"β␈↓ α␈↓␈↓ α`                         ii)  If the tail is a prefix of the corresponding ␈↓εb␈↓βi␈↓,
␈↓"β␈↓ α␈↓␈↓ α`                            enter the ␈↓αnew␈↓ tail (i.e., what is left of ␈↓εb␈↓βi␈↓ after
␈↓"β␈↓ α␈↓␈↓ α`                            deleting the tail from the front of it) in (n+1)␈↓βα␈↓.
␈↓"β␈↓ α␈↓␈↓ α`                        iii)  If the corresponding ␈↓εb␈↓βi␈↓ is a prefix of the tail,
␈↓"β␈↓ α␈↓␈↓ α`                            enter the new tail in (n+1)␈↓ββ␈↓.
␈↓"β␈↓ α␈↓␈↓ α`                a3)  If any ␈↓εa␈↓βi␈↓ is a prefix of any string in n␈↓βα␈↓, add the corre-
␈↓"β␈↓ α␈↓␈↓ α`                   sponding ␈↓εb␈↓βi␈↓ to the end of the tail, and enter the whole thing
␈↓"β␈↓ α␈↓␈↓ α`                   in column (n+1)␈↓βα␈↓. (e.g. In Figure 2, the entry "1111" in column
␈↓"β␈↓ α␈↓␈↓ α`                   2␈↓βα␈↓, results from "1", in 0␈↓βα␈↓, being a prefix of "11", in 1␈↓βα␈↓,
␈↓"β␈↓ α␈↓␈↓ α`                   thus "111", ␈↓εb␈↓β1␈↓, was added to the tail "1". Again, in 3␈↓βα␈↓,
␈↓"β␈↓ α␈↓␈↓ α`                   "1", in 0␈↓βα␈↓, is a prefix of "1111", in 2␈↓βα␈↓, so "111", ␈↓εb␈↓β1␈↓,
␈↓"β␈↓ α␈↓␈↓ α`                   is added to the tail, producing the entry "111111".)
␈↓"β␈↓ α␈↓␈↓ α`    
␈↓"β␈↓ α␈↓␈↓ α`                b1)  If any string in n␈↓ββ␈↓ is an ␈↓εb␈↓βi␈↓, write the corresponding ␈↓εa␈↓βi␈↓ in
␈↓"β␈↓ α␈↓␈↓ α`                   column (n+1)␈↓ββ␈↓. (e.g. In column 1␈↓ββ␈↓, "111" appears, thus "1",
␈↓"β␈↓ α␈↓␈↓ α`                   the corresponding ␈↓εa␈↓βi␈↓, appears in 2␈↓ββ␈↓.)
␈↓"β␈↓ α␈↓␈↓ α`                b2)  If any string in n␈↓ββ␈↓ is a prefix of any ␈↓εb␈↓βi␈↓, check the tail:
␈↓"β␈↓ α␈↓␈↓ α`                          i)  If the tail is the corresponding ␈↓εa␈↓βi␈↓, then we have
␈↓"β␈↓ α␈↓␈↓ α`                            a solution!
␈↓"β␈↓ α␈↓␈↓ α`                         ii)  If the tail is a prefix of the corresponding ␈↓εa␈↓βi␈↓,
␈↓"β␈↓ α␈↓␈↓ α`                            enter the ␈↓αnew␈↓ tail in (n+1)␈↓ββ␈↓.
␈↓"β␈↓ α␈↓␈↓ α`                        iii)  If the corresponding ␈↓εa␈↓βi␈↓ is a prefix of the tail,
␈↓"β␈↓ α␈↓␈↓ α`                            enter the new tail in (n+1)␈↓βα␈↓. (e.g. In Figure 2,
␈↓"β␈↓ α␈↓␈↓ α`                            column 2␈↓ββ␈↓ contains "1", which is a prefix of ␈↓εb␈↓β1␈↓;
␈↓"β␈↓ α␈↓␈↓ α`                            the tail is "11"; the corresponding ␈↓εa␈↓β1␈↓ is "1",
␈↓"β␈↓ α␈↓␈↓ α`                            which is a prefix of the tail "11", thus the ␈↓αnew␈↓
␈↓"β␈↓ α␈↓␈↓ α`                            tail is "1" and is entered in 3␈↓βα␈↓.)
␈↓"β␈↓ α␈↓␈↓ α`                b3)  If any ␈↓εb␈↓βi␈↓ is a prefix of any string in n␈↓ββ␈↓, add the corre-
␈↓"β␈↓ α␈↓␈↓ α`                   sponding ␈↓εa␈↓βi␈↓ to the end of the tail, and enter the whole thing
␈↓"β␈↓ α␈↓␈↓ α`                   in column (n+1)␈↓ββ␈↓.
␈↓"β␈↓ α␈↓␈↓ α`    
␈↓"β␈↓ α␈↓To␈α∞facilitate␈α∞the␈α∞construction␈α∞of␈α∞our␈α∂solution␈α∞we␈α∞subscript␈α∞each␈α∞entry␈α∞in␈α∞the␈α∂table␈α∞with␈α∞the␈α∞index␈α∞of␈α∞the␈α∞pair␈α∂used␈α∞in
␈↓ α␈↓deriving␈α
it.␈α
 We␈α
also␈α∞use␈α
arrows␈α
to␈α
trace␈α∞the␈α
history␈α
of␈α
entries.␈α∞Then,␈α
when␈α
we've␈α
found␈α∞that␈α
a␈α
solution␈α
exists,␈α∞we␈α
can
␈↓ α␈↓simply␈αfollow␈αthe␈αpath␈αfrom␈αthe␈αfirst␈αcolumn␈αpair,␈αnoting␈αthe␈αsubscripts␈αas␈αwe␈αgo,␈αand␈αwe␈αare␈αleft␈αwith␈αthe␈αdesired␈αlist␈αof
␈↓ α␈↓indices. If a solution exists, it must be constructable by the given rules.
␈↓"β␈↓ α␈↓␈↓ α`    
␈↓"β␈↓ α␈↓␈↓ α`        0␈↓βα␈↓    0␈↓ββ␈↓        1␈↓βα␈↓    1␈↓ββ␈↓       2␈↓βα␈↓      2␈↓ββ␈↓      3␈↓βα␈↓      3␈↓ββ␈↓      4␈↓βα␈↓    4␈↓ββ␈↓
␈↓"β␈↓ α␈↓␈↓ α`     ___________________________________________________________________
␈↓"β␈↓ α␈↓␈↓ α`    
␈↓"β␈↓ α␈↓␈↓ α`         1     111      11␈↓β(1)␈↓          1111␈↓β(1)␈↓      111111␈↓β(1)␈↓
␈↓"β␈↓ α␈↓␈↓ α`     10111     10             111␈↓β(2)␈↓          1␈↓β(1)␈↓      1␈↓β(1)␈↓         111␈↓β(1)␈↓
␈↓"β␈↓ α␈↓␈↓ α`        10       0                                                          *␈↓β(3)␈↓
␈↓"β␈↓ α␈↓␈↓ α`    
␈↓"β␈↓ α␈↓␈↓ α`                                        Figure 2.
␈↓ α␈↓␈↓ 
{␈↓  6␈↓

␈↓"β␈↓ α␈↓␈↓ α`    
␈↓"β␈↓ α␈↓␈↓ α`When␈αa␈αsolution␈αdoes␈αnot␈αexist,␈αwe␈αmay␈αor␈αmay␈αnot␈αbe␈αable␈αto␈αdetermine␈αso.␈α The␈αtable␈αmight␈α"close␈αout"␈αafter␈αa
␈↓ α␈↓finite␈α∞number␈α∞of␈α∞steps,␈α∞that␈α∞is,␈α∞there␈α∞may␈α∞be␈α∞no␈α∞more␈α∞possible␈α∞entries.␈α∞ In␈α∞this␈α∞case␈α∞there␈α∞is␈α∞no␈α∞solution.␈α∞ The␈α∞column
␈↓ α␈↓generating␈αprocess␈αmight␈αalso␈αcontinue␈αad␈αinfinitum;␈αthis␈αis␈αdetectable␈αin␈αspecial␈αcases␈αbut␈αnot␈αin␈αgeneral.␈αFor␈αexample,␈αif
␈↓ α␈↓any column-pair is ever repeated, there is no solution.
␈↓"β␈↓ α␈↓␈↓ α`The␈α
difficulties␈α
arise␈α
in␈α∞step␈α
3)␈α
parts␈α
a3)␈α
and␈α∞b3).␈α
 The␈α
entries␈α
afforded␈α
by␈α∞these␈α
rules,␈α
and␈α
thus␈α
the␈α∞tails␈α
used
␈↓ α␈↓elsewhere, can grow arbitrarily long, thus ruining our chances for a guarantee of termination of the process.
␈↓"β␈↓ α␈↓␈↓ α`Of␈α∞course,␈α∞we␈α∂have␈α∞not␈α∞shown␈α∂that␈α∞the␈α∞problem␈α∞is␈α∂unsolvable.␈α∞ The␈α∞motive␈α∂for␈α∞introducing␈α∞a␈α∂partial␈α∞decision
␈↓ α␈↓procedure␈αis␈αto␈αoffer␈αstudents␈αsome␈αinsight␈αinto␈αthe␈αproblem␈αitself.␈α The␈αproof␈αof␈αunsolvability␈αmay␈αthen␈αbe␈αpresented␈αas
␈↓ α␈↓usual, by reduction to the Halting Problem or some other class of problems known to the students.
␈↓"β␈↓ α␈↓␈↓ πO␈↓	References␈↓






␈↓"β␈↓ α␈↓Huffman, D., IS10:Introduction to Cybernetics, Information Sciences Board,
␈↓"β␈↓ α␈↓        University of California at Santa Cruz, Spring Quarter, 1978.
␈↓"β␈↓ α␈↓     
␈↓"β␈↓ α␈↓Manna, Z., ␈↓αMathematical Theory of Computation␈↓, McGraw-Hill, New York,
␈↓"β␈↓ α␈↓        New York, 1974.
␈↓"β␈↓ α␈↓                                                                           
␈↓"β␈↓ α␈↓Minsky, M., ␈↓αComputation: Finite and Infinite Machines␈↓, Prentice-Hall, Inc.,
␈↓"β␈↓ α␈↓        Englewood Cliffs, New Jersey, 1967.
␈↓ α␈↓␈↓ 
{␈↓  7␈↓